package com.lans.SortAlgorithm;

import java.util.Arrays;

/*
 * @author: lans
 * @date: 2025/1/20
 * @name: 刘宇
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arrays = new int[]{2, 6, 4, 1, 3, 7, 5};
        insertSort(arrays);
        System.out.println(Arrays.toString(arrays));
    }

    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i]; // 当前要插入的元素
            int j = i - 1;//已经排序好的元素-1
            // 将arr[i]插入到已排序序列arr[0..i-1]中
            while (j >= 0 && arr[j] > key) {
                //跳出循环的情况:j=-1/j已经到该待的位置
                arr[j + 1] = arr[j]; // 将大于key的元素向后移动
                j = j - 1;//索引向左移动 与更前面的元素进行比较
            }
            arr[j + 1] = key; // 插入key到正确的位置
        }
    }
}